/*
 *https://leetcode.cn/problems/accounts-merge/
 *lc721. 账户合并
 *medium 吴朝泽 2024.9.30
 *并查集
*/

class union_find
{
    vector<int> parent;
    int group;
public:

    // 构造从 0 到 n - 1 的节点
    union_find(int n) :
        parent(n), group()
    {
        for (int i = 0; i < n; ++i)
        {
            parent[i] = i;
        }
        group = n;
    }

    // 合并两个节点
    void pair(int index1, int index2)
    {
        int root_1 = find(index1), root_2 = find(index2);
        if (root_1 != root_2)
        {
            --group;
        }
        parent[root_2] = root_1;
    }

    // 找到根节点
    int find(int index)
    {
        vector<int> temp;

        int root = index;
        for (; parent[root] != root; root = parent[root])
        {
            temp.emplace_back(root);
        }

        for (auto& it : temp)
        {
            parent[it] = root;
        }

        return root;
    }

    // 判断连接性
    bool check(int index1, int index2)
    {
        return find(index1) == find(index2);
    }

    // 返回连通图的数量
    int group_count()
    {
        return group;
    }
};

class Solution {
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        int n = accounts.size();  // 获取账户数量
        union_find uf(n);        // 创建并查集对象
        
        unordered_map<string, int> email_to_index; // 邮箱到账户索引的映射

        // 第一步：构建邮箱与账户的连接关系
        for (int i = 0; i < n; ++i) 
        {
            for (int j = 1; j < accounts[i].size(); ++j) 
            {
                string email = accounts[i][j]; // 当前账户的邮箱
                // 如果该邮箱已经存在于映射中，合并两个账户
                if (email_to_index.find(email) != email_to_index.end()) 
                    uf.pair(i, email_to_index[email]);
                
                // 更新邮箱对应的账户索引
                email_to_index[email] = i; 
            }
        }

        
        // 第二步：收集每个根账户的所有邮箱
        unordered_map<int, set<string>> merged_accounts;
        for (auto& [email, index] : email_to_index)
        {
            int root = uf.find(index); // 查找当前邮箱对应账户的根节点
            merged_accounts[root].insert(email); // 将邮箱加入到根账户的集合中
        }

        // 第三步：构建结果
        vector<vector<string>> result;
        for (auto& [root, emails] : merged_accounts) 
        {
            vector<string> merged_account;
            merged_account.push_back(accounts[root][0]); // 添加账户名称
            
            // 将所有邮箱添加到合并后的账户中
            merged_account.insert(merged_account.end(), emails.begin(), emails.end());
            
            // 按字典顺序排序邮箱
            sort(merged_account.begin() + 1, merged_account.end()); 
            result.push_back(merged_account); // 将合并后的账户添加到结果中
        }

        return result; // 返回最终结果
    }
};
